// https://www.lintcode.com/problem/triangle/description

class Solution {
public:
    /**
     * @param triangle: a list of lists of integers
     * @return: An integer, minimum path sum
     */
    int minimumTotal(vector<vector<int>> &triangle) {
        // 法一：从上往下
        int len = triangle.size();
        vector<vector<int>> result(len, vector<int>(len, 0));
        result[0][0] = triangle[0][0];
        for (int i = 1; i < len; ++i)
        {
            result[i][0] = result[i - 1][0] + triangle[i][0];
            result[i][i] = result[i - 1][i - 1] + triangle[i][i];
        }
        for (int i = 1; i < len; ++i)
        {
            for (int j = 1; j < i; ++j)
            {
                result[i][j] += min(result[i - 1][j - 1], result[i - 1][j]) + triangle[i][j];
            }
        }
        int minVal = INT_MAX;
        for (int i = 0; i < len; ++i)
        {
            if (result[len - 1][i] < minVal) minVal = result[len - 1][i];
        }
        return minVal;
        
        // 法二：用triangle记
        
        // 法三：从下往上。result需要更新的值越来越少，最后只剩下一个，空间复杂度O(N)
        // int len = triangle.size();
        // int *result = new int[len];
        // for (int i = 0; i < len; i++){
        //     result[i] = triangle[len - 1][i];
        // }
        // for (int i = len - 2; i >= 0; i--){
        //     for (int j = 0; j <= i; j++){
        //         result[j] = triangle[i][j] + min(result[j], result[j + 1]);
        //     }
        // }
        // return result[0];
    }
};